package create.randomizedSet;

import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;

/**
 * @Time 2020/1/4
 * @author 王光浩
 * @Need 创建一个数据结构，该数据结构要求插入和删除元素的平均时间复杂度为O（1），另外需要一个从集合中随机
 *       获取元素的方法，该方法获取每一个数据的概率要一致。
 *       思路：使用Set。
 *       boolean insert（int val）：向Set中插入一个数据，数据不存在则返回true，并且插入元素，否则返回
 *                                  false，不插入元素。
 *       boolean remove(int val):从Set中删除一个数据，数据不存在返回fale，存在返回true。
 *    
 *       int getRandom()：获取Set的长度，然后根据长度获取一个随机数，随后遍历Set，当经过
 *                        随机数-1个元素后，将第随机数个元素返回。
 *       获取一个随机的value值的时间复杂度为O（n）
 *
 */
public class RandomizedSet {
	private Set<Integer> set;
	private Random rand;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        set=new HashSet<Integer>();
        rand=new Random();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
       return set.add(val);
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        return set.remove(val);
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int count=rand.nextInt(set.size());
        int ans=0;
        for(int i:set) {
        	if(count==0)
        		ans=i;
        	count--;
        }
        return ans;
    }
    
}
